Dictionnaires

Table des matières

1. Définition

Les dictionnaires de Python sont des structures de données qui associent des valeurs à des clés. 

# Création d'un dictionnaire qui associe à la clé "France" la valeur "Paris"
# et à la clé "Allemagne" la valeur "Berlin"
In [1]: capitale = {"France": "Paris", "Allemagne": "Berlin"}

In [2]: capitale["France"] # indexation du dictionnaire par une clé
Out[2]: 'Paris'
In [3]: capitale["Allemagne"]
Out[3]: 'Berlin'
In [4]: capitale["Espagne"] # le dictionnaire ne contient pas la clé "Espagne"
KeyError: 'Espagne'

In [1]: annuaire = {"Yves Dupont": 0123456789, "Anaïs Duplan": 0798654321}
In [2]: dictionnaire = {} # le dictionnaire vide

Dans un dictionnaire,

  • les valeurs peuvent être de n'importe quel type (int, float, str, couple d'entiers, liste, dictionnaire)
  • les clefs ne peuvent pas être des listes/des dictionnaires. Les autres types usuels sont possibles. Il faut en fait que la clé soit hachable, donc au moins immutable.

Les clés et les valeurs d'un dictionnaire ne sont pas nécessairement du même type, ce qui permet d'utiliser des dictionnaires pour représenter des types de données complexe. 

# On représente une note par un dictionnaire
In [1]: note = {"valeur": 15, "coefficient": 1.5, "matière": "math"}
In [2]: note["valeur"] * note["coefficient"]
Out[2]: 22.5

Écrire une fonction moyenne_math, qui prend en argument une liste l de notes représentées par des dictionnaires, de clés "valeur", "coefficient" et "matière" et qui renvoie la moyenne pondérée des notes obtenues dans la matière "math".

La moyenne des $(x_i)_{1\leq i\leq n}$ pondérée par les $(y_i)_{1\leq i\leq n}$ est $\frac{\sum\limits_{i=1}^n x_i y_i}{\sum\limits_{i=1}^n y_i}$.

2. Opérations

2.1. Opérations élémentaires

Indexation
L'expression dict[key] renvoie la valeur associée à la clé key, si elle est présente dans le dictionnaire.
Affectation
L'instruction dict[key] = value ajoute la clé key au dictionnaire et lui associe la valeur value. Si la clé était déjà présente dans le dictionnaire, la valeur associée est modifiée.
Suppression
L'instruction dict.pop(key) retire la clé du dictionnaire, et renvoie la valeur associée à cette clé.

2.2. Clés d'un dictionnaire

  • On peut obtenir le nombre de clés d'un dictionnaire avec l'instruction len(dict).
  • On peut tester si un dictionnaire contient une clé avec les expressions key in dict et key not in dict.

Les opérations élémentaires (indexation, affectation, suppression), le calcul de la taille (len(dict)) et les tests key in dict s'effectuent tous en temps constant (contrairement aux listes, pour le dernier). 

# associe la valeur val à la clé key dans le dictionnaire dic
# seulement si cette clé n'est pas déjà présente dans le dictionnaire
def ajoute_si_absent(dic, key, val):
    if key not in dic:
        dic[key] = val

Les notes des élèves d'une classe sont représentées par un dictionnaire notes dont les clés sont des chaînes de caractères, et les valeurs des listes de notes :

notes = {"Alice": [10.,15.,13.], "Bob": [13., 9., 16.], …}

Écrire un extrait de code qui utilise le dictionnaire notes et détermine le nombre de notes de Bob. On traitera correctement le cas où "Bob" n'est pas une clé du dictionnaire.

On appelle puissance parfaite tout entier de la forme $a^b$, où $a\in\N$ et $b\geq 2$. On appelle exposant d'une puissance parfaite $n$ le plus grand exposant $b\geq 2$ tel que $n$ puisse s'écrire sous la forme $n = a^b$, pour $a\in\N$.

Par exemple, $16 = 2^4$ et $16 = 4^2$, donc $16$ est une puissance parfaite, d'exposant $4$.

  1. Écrire une fonction puissances_parfaites qui prend en argument un entier $n$ et renvoie un dictionnaire, dont les clés sont les puissances parfaites $a^b$ inférieures à $n$, et les valeurs sont les exposants $b$ associés.

  2. En utilisant la question précédente, écrire un extrait de code vérifiant le cas particulier de la conjecture de Beal 1 suivant :

    Si $1\leq x,y\leq 1000$ et si $x^3 + y^3$ est une puissance parfaite, alors soit $x,y$ ont un diviseur commun $\gt 1$, soit cette puissance parfaite est d'exposant $2$.

    On pourra par exemple afficher "Contre-exemple !" si l'on trouve un contre-exemple à la conjecture de Beal.

    Pour tester si $x$ et $y$ ont un diviseur commun $\gt 1$, on utilisera la fonction math.gcd qui calcule le pgcd : $x$ et $y$ ont un diviseur commun $\gt 1$ si et seulement si math.gcd(x,y) > 1.

  3. Pour vérifier cette conjecture de Beal, au lieu de générer le dictionnaire de la première question, on aurait pu

    1. générer une liste de toutes les puissances parfaites d'exposant $\geq 3$.
    2. générer une liste l de booléens de taille $2 \times 1000^3$ telle que l[i] contienne True si et seulement si i est une puissance parfaite d'exposant $\geq 3$.

    Quels sont les inconvénients et avantages de chaque méthode ?

On peut combiner les deux alternatives de la question 3. comme suit. Si l'on sait d'avance que l'on va trouver environ 100 puissances parfaites, on crée une liste l de taille 100, dont les éléments sont des listes (initialement, l contient 100 listes vides). Lorsque l'on trouve une puissance parfaite $a^b$, on calcule son reste $r$ modulo 100, et on ajoute $a^b$ à la liste l[r].

Cette représentation a un coût mémoire optimal, et une fois la liste l construite, on peut tester si un entier n est une puissance parfaite en temps constant (en moyenne) : il suffit de calculer le reste r de n modulo $100$, et de tester si n appartient à la liste l[r], qui devrait ne contenir que très peu d'éléments (puisqu'on a fait l'hypothèse qu'il n'y aurait que 100 puissances parfaites à stocker).

C'est en fait comme cela qu'est implémenté le type dictionnaire : une fonction de hachage transforme les clés en des entiers, qui sont les indices d'une liste de listes (chaque sous-liste étant appelée un seau/bucket). Comme Python ne sait pas par avance combien de clés est-ce que le dictionnaire contiendra, la représentation est modifiée régulièrement lorsque le nombre de clés augmente : dans l'exemple précédent, si le nombre de puissances parfaites dépasse 1000, on recrée une liste de taille 1000, et on utilise les restes modulo 1000 plutôt que 100.

2.3. Copie

Comme pour une liste,

  • on peut copier un dictionnaire d avec la méthode copy : dbis = d.copy().
  • cette copie est superficielle : si les valeurs de d sont mutables, la modification d'une valeur de dbis la modifie aussi dans d.
In [1]: d = {0: "a", 1: "b"}
In [2]: dbis = d.copy()
In [3]: dbis[0] = "c"
In [4]: d # d n'est pas modifié
Out[4]: {0: 'a', 1: 'b'}

In [1]: d = {0: [0], 1: [1]}
In [2]: dbis = d.copy()
In [3]: dbis[0].append(3)
In [4]: d # d[0] a été modifié
Out[4]: {0: [0, 3], 1: [1]}

In [1]: d = {0: [0], 1: [1]}
In [2]: dbis = d.copy()
In [3]: dbis[0] = [3]
In [4]: d # d[0] n'est pas modifié
Out[4]: {0: [0], 1: [1]}

3. Itération

Les méthodes keys(), values() et items() permettent d'itérer sur les clés, les valeurs ou les couples (clé, valeur) d'un dictionnaire.

Les extraits suivants utilisent un dictionnaire d = {"François": "Mitterrand", "Jacques": "Chirac"}. 

In [1]: for x in d.keys():
   ...:     print(x)
   ...:
François
Jacques

In [1]: for x in d.values():
   ...:     print(x)
   ...:
Mitterrand
Chirac

In [1]: for x,y in d.items():
   ...:     print(x,y)
   ...:
François Mitterrand
Jacques Chirac

En fait, on peut itérer sur les clés d'un dictionnaire avec la syntaxe for x in d, les extraits précédents peuvent donc s'écrire de la manière plus simple suivante, à préférer. 

In [1]: for x in d:
   ...:     print(x)
   ...:
François
Jacques

In [1]: for x in d:
   ...:     print(d[x])
   ...:
Mitterrand
Chirac

In [1]: for x in d:
   ...:     print(x,d[x])
   ...:
François Mitterrand
Jacques Chirac

La syntaxe [x for x in d] permet de créer une liste des clés de d. 

In [1]: [x for x in d]
Out[1]: ['François', 'Jacques']

In [1]: [d[x] for x in d]
Out[1]: ['Mitterrand', 'Chirac']

\newpage

On suppose défini un dictionnaire pop = {"Paris" : 2000000, "Lyon": 500000, ...}.

  1. Écrire du code Python qui affiche les noms des villes de plus de 100 000 habitants.
  2. Écrire du code qui détermine la population minimale.
  3. Écrire du code qui affiche une ville de population minimale.

On suppose définis deux dictionnaires

  • troupeau = {"vache": 33, "poule": 47, ...}
  • nb_pattes = {"vache": 4, "poule": 2, ...}.

Écrire du code Python qui détermine le nombre de pattes total du troupeau.

On suppose définis deux dictionnaires

  • regne = {"Chirac" : (1995, 2007), "Mitterrand": (1981, 1995), ...} qui au nom d'un président français associe le couple des années de début et de fin d'office.
  • pib = {1981: 1.13, ...} qui à chaque année associe l'augmentation annuelle du PIB national cette année, en pourcentage.

Écrire du code Python qui crée un nouveau dictionnaire, qui associe à chaque nom d'un président français l'augmentation totale en pourcentage du PIB national pendant sa période d'office.

4. Utilisation d'un dictionnaire comme ensemble ou compteurs

On peut utiliser un dictionnaire pour représenter un ensemble (au sens mathématique) de données, c'est-à-dire une collection de données sans doublons. Les données seront les clés du dictionnaire, et les valeurs n'ont pas d'importance. On peut utiliser comme valeur l'objet None de Python qui représente une absence de valeur.

L'extrait de gauche illustre ce principe. L'extrait de droite utilise une liste pour représenter un ensemble. S'il y avait plus de valeurs, il serait moins performant, car pour une liste, les instructions e in l ont une complexité linéaire — si la liste contenait les 100 000 premiers nombres premiers, le test 6 in liste_premiers devrait comparer 6 à chacun des 100 000 éléments de la liste alors que le test 6 in dict_premiers s'exécute en temps constant. 

In [1]: dict_premiers = {2: None, 3: None, 5: None, 7: None}
In [2]: 5 in dict_premiers
Out[2]: True
In [2]: 6 in dict_premiers
Out[2]: False
In [3]: len(dict_premiers)
Out[3]: 4

In [1]: liste_premiers = [2,3,5,7]
In [2]: 5 in liste_premiers
Out[2]: True
In [2]: 6 in liste_premiers
Out[2]: False
In [3]: len(liste_premiers)
Out[3]: 4

On cherche à déterminer le nombre d'éléments distincts d'une liste d'entiers. Par exemple, la liste [1,2,2,3,1,0,2] contient $4$ éléments distincts.

  1. En construisant un dictionnaire, écrire une fonction nb_elem_distincts qui prend en argument une liste (dont les éléments sont hachables) et renvoie le nombre d'éléments distincts de cette liste. La complexité sera linéaire.

    Pour la liste [1,2,2,3,1,0,2], on construira le dictionnaire {1: None, 2:None, 3:None, 0:None}.

  2. Expliquer pourquoi la fonction nb_elem ci-contre compte le nombre d'éléments distincts d'une liste. Quelle est sa complexité ?
  3. Proposer une idée d'un autre algorithme possible pour compter le nombre d'éléments distincts d'une liste, sans utiliser de dictionnaire et avec une complexité meilleure que quadratique.
def nb_elem(l):
    c, n = 0, len(l)
    for i in range(n):
        if l[i] not in l[:i]:
            c += 1
    return c

Écrire une fonction plus_commun qui prend en argument une liste non vide et renvoie un élément qui apparaît le plus souvent dans cette liste. On veut une complexité linéaire. 2

assert(plus_commun([1,5,4,1,5,2,3,5]) == 5)

5. Exercices

Écrire une fonction qui prend en argument un dictionnaire medecin, dont les clés sont des chaînes de caractères représentant le nom d'une personne et la valeur associée est le nom de son médecin traitant et qui renvoie un dictionnaire patients dont les clés sont les noms des médecins, et dont les valeurs sont les listes de leurs patients.

On suppose donné un dictionnaire dettes dont les clés sont des chaînes de caractères représentant des personnes et dont les valeurs sont des dictionnaires, dont les clés sont des noms de personnes et les valeurs des entiers naturels, représentant la dette due.

Par exemple, dettes["Bob"] = {"Alice": 16, "Jean": 12} signifie que Bob doit 16 € à Alice et 12 € à Jean.

  1. Écrire du code Python qui détermine la personne la plus endettée.
  2. Écrire du code Python qui détermine la personne la plus fortunée, une fois toutes les dettes payées.

Bob joue avec un deck de $52 = 4\times 13$ cartes. Il tire les cartes au fur à mesure, et jette les cartes tirées. Dans un dictionnaire d, il conserve des informations sur les cartes déjà tirées. Les clés de d sont les entiers de 1 à 10 et les chaînes "K", "Q" et "J" (pour roi, reine et valet). La valeur associée à chaque clé est le nombre de carte de cette valeur qui ont déjà été tirées.

  1. Écrire une fonction qui prend en argument le dictionnaire d et renvoie le nombre de cartes restantes.
  2. Écrire une fonction qui prend en argument le dictionnaire d et renvoie True s'il est possible que les quatre prochaines cartes aient la même valeur.

Écrire une fonction qui prend en argument une liste de couples d'entiers, représentant des points dans $\R^2$ et qui renvoie la distance la plus souvent atteinte entre deux points. On évitera d'utiliser des flottants comme clefs dans le dictionnaire.

  1. Écrire une fonction association_injective qui prend en argument un dictionnaire d et renvoie True si et seulement si l'association clef -> valeur représentée par le dictionnaire est injective.
  2. Écrire une nouvelle version, avec une complexité linéaire, sous une hypothèse à préciser sur les types des clefs et/ou des valeurs de d.

On suppose donnés deux dictionnaires spam_freq et freq, dont les clés sont des mots français. Le dictionnaire freq associe à chaque mot $w$ la probabilité $P(w)$ que le mot $w$ apparaisse dans un mail, le dictionnaire spam_freq associe à $w$ la probabilité $P(w|S)$ que le mot apparaisse dans un mail de spam.

Étant donné le texte d'un mail, noté $m$, composé de mots $w_1,\dots, w_n$, la probabilité que $m$ soit un message de spam est estimée par la formule $$P(S) = \frac{1}{2}\frac{\prod_{i=1}^n P(w_i|S)}{P(w_i)}.$$

Écrire une fonction filtre qui prend en argument une chaîne de caractère représentant le texte d'un email, et renvoie True si ce message a une probabilité $\geq 0.5$ d'être du spam.

On supposera que le texte ne contient pas de ponctuation et on utilisera la méthode split pour obtenir une liste des mots du message :

"ceci est un essai".split() == ["ceci", "est", "un", "essai"]

Sous-chaînes et anagrammes

Écrire une fonction qui prend en argument une chaîne de caractères et qui renvoie le nombre de sous-chaînes de longueur 3 distinctes de celle-ci.

Écrire une fonction est_anagramme qui prend en argument deux chaînes de caractères et qui renvoie True si ces chaînes sont anagrammes l'une de l'autre, c'est-à-dire que l'une peut s'obtenir à partir de l'autre en réordonnant ses lettres.

  1. Écrire une première version en utilisant un dictionnaire. Complexité ?
  2. Écrire une seconde version en utilisant l'instruction décrite ci-dessous. Complexité ?

Si c est une chaîne de caractères, l'instruction sorted(c) renvoie une liste, dont les éléments sont les lettres de c, triées par ordre alphabétique.

sorted("baba") == ["a", "a", "b", "b"].

Écrire une fonction qui prend en argument une chaîne de caractères et renvoie True si elle contient toutes les permutations d'une chaîne de longueur 3.

On veut une complexité linéaire.

Autres

Écrire une fonction qui prend en argument une chaîne de caractères, et renvoie la longueur de la plus grande sous-chaîne de c qui ne contient que des lettres distinctes. On veut une complexité linéaire.

Écrire une fonction nb_points_alignes qui prend en argument une liste de couples d'entiers, représentant les coordonnées de points dans le plan et qui renvoie le plus grand nombre de ces points qui sont alignés, avec une complexité quadratique. On veut une solution exacte, sans utiliser le calcul flottant.

Notes de bas de page:

1

l'équation $x^n + y^m = z^p$ n'a pas de solutions entières avec $n,m,p\geq 3$ et $x,y,z$ premiers entre eux. C'est une généralisation du (grand) théorème de Fermat.

2

Construire un dictionnaire dont les clés sont les éléments de la liste et les valeurs sont le nombre de fois où on a trouvé l'élément.